Grokking Google Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Google Easy
Add Binary (easy)
Solution: Add Binary
Valid Mountain Array (easy)
Solution: Valid Mountain Array
Set Mismatch (easy)
Solution: Set Mismatch
Is Subsequence (easy)
Solution: Is Subsequence
Length of Last Word (easy)
Solution: Length of Last Word
Search Insert Position (easy)
Solution: Search Insert Position
Repeated Substring Pattern (easy)
Solution: Repeated Substring Pattern
Monotonic Array (easy)
Solution: Monotonic Array
Count Nodes Equal to Average of Subtree (easy)
Solution: Count Nodes Equal to Average of Subtree
Find the Difference (easy)
Solution: Find the Difference
How Many Numbers Are Smaller Than the Current Number (easy)
Solution: How Many Numbers Are Smaller Than the Current Number
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Find the Difference of Two Arrays (easy)
Solution: Find the Difference of Two Arrays
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Google Medium
Gray Code (medium)
Solution: Gray Code
2 Keys Keyboard (medium)
Solution: 2 Keys Keyboard
Arithmetic Slices (medium)
Solution: Arithmetic Slices
Unique Length-3 Palindromic Subsequences (medium)
Solution: Unique Length-3 Palindromic Subsequences
Minimum Difference Between Largest and Smallest Value in Three Moves (medium)
Solution: Minimum Difference Between Largest and Smallest Value in Three Moves
Letter Combinations of a Phone Number (medium)
Solution: Letter Combinations of a Phone Number
01 Matrix (medium)
Solution: 01 Matrix
Maximum Points You Can Obtain from Cards (medium)
Solution: Maximum Points You Can Obtain from Cards
Strobogrammatic Number II (medium)
Solution: Strobogrammatic Number II
Maximum Length of Semi-Decreasing Subarrays (medium)
Solution: Maximum Length of Semi-Decreasing Subarrays
Minimum Area Rectangle (medium)
Solution: Minimum Area Rectangle
Count Unreachable Pairs of Nodes in an Undirected Graph (medium)
Solution: Count Unreachable Pairs of Nodes in an Undirected Graph
Single Number II (medium)
Solution: Single Number II
4Sum II (medium)
Solution: 4Sum II
Furthest Building You Can Reach (medium)
Solution: Furthest Building You Can Reach
Minimizing Array After Replacing Pairs With Their Product (medium)
Solution: Minimizing Array After Replacing Pairs With Their Product
Fair Distribution of Cookies (medium)
Solution: Fair Distribution of Cookies
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Rotate Image (medium)
Solution: Rotate Image
Combination Sum (medium)
Solution: Combination Sum
Implement Trie (Prefix Tree) (medium)
Solution: Implement Trie (Prefix Tree)
Number of Islands (medium)
Solution: Number of Islands
Edit Distance (medium)
Solution: Edit Distance
Container With Most Water (Medium)
Solution: Container With Most Water
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Shortest Subarray with Sum at Least K (hard)
Solution: Shortest Subarray with Sum at Least K
Reverse Pairs (hard)
Solution: Reverse Pairs
Nth Magical Number (hard)
Solution: Nth Magical Number
Candy (hard)
Solution: Candy
Arithmetic Slices II - Subsequence (hard)
Solution: Arithmetic Slices II - Subsequence
Burst Balloons (hard)
Solution: Burst Balloons
Sum of Distances in Tree (hard)
Solution: Sum of Distances in Tree
Maximum Score of a Good Subarray (hard)
Solution: Maximum Score of a Good Subarray
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Solution: Minimum Difference Between Largest and Smallest Value in Three Moves

Problem Statement

You are given an integer array nums. You're allowed to change any of the numbers up to three times, turning them into any value you wish.

Return the minimum difference between the largest and smallest value of nums after updating the nums array.

Examples

  • Example 1:

    • Input: [1,5,6,14,15]
    • Expected Output: 1
    • Justification: Change the numbers 14 and 15 to 2 and 3, respectively (or similarly small numbers). Now, the array is [1,2,3,5,6] with a minimum difference of 5 - 1 = 4.
  • Example 2:

    • Input: [10,10,10,10,10]
    • Expected Output: 0
    • Justification: All numbers are the same, so even without any moves, the difference is already 0.
  • Example 3:

    • Input: [1,100,200,300,400]
    • Expected Output: 99
    • Justification: Change the three highest values to any number between 1 and 100 (inclusive). For simplicity, changing 200, 300, and 400 to 2, 3, and 4 respectively will make the array [1,2,3,4,100], with a minimum difference of 100 - 1 = 99.

Solution

To solve this problem, the most straightforward approach is to sort the array. Sorting allows us to easily identify the candidates for modification (the largest and smallest values). We aim to minimize the gap between the smallest and largest numbers with up to three changes. Intuitively, it makes sense to either elevate the smallest numbers or reduce the largest ones. However, instead of directly changing values, we can analyze the effect of such changes by considering the possible scenarios after zero to three modifications.

This approach works because the relative difference we're trying to minimize becomes clear once the array is sorted. We'll compare the potential minimum differences after no change, one change, two changes, and three changes to find the smallest possible outcome. This strategy is effective because it leverages the sorted order to minimize the range efficiently, addressing the problem's core challenge without the need for direct value manipulation.

Step-by-Step Algorithm

  1. Check for Edge Case: If the array length is 4 or fewer, return 0 because we can make all elements equal by performing up to three modifications.

  2. Sort the Array: Sort the array in non-decreasing order to easily identify the smallest and largest values.

  3. Calculate Potential Minimum Differences: Evaluate the minimum difference possible after performing up to three modifications by considering the following scenarios:

    • Convert the three smallest elements to the fourth smallest element. This scenario removes the influence of the three smallest numbers.

    • Convert the three largest elements to the fourth largest element. This effectively removes the influence of the three largest numbers.

    • Convert the largest element to the second largest element and the two smallest elements to the third smallest element.

    • Convert the two largest elements to the third largest element and the smallest element to the second smallest element.

  4. Determine the Minimum Difference: Among the differences calculated in the scenarios above, find and return the smallest one as the minimum possible difference after performing up to three moves.

Algorithm Walkthrough

Let's consider the Input: nums = [1,5,6,14,15]

  1. Check for Edge Case: The array has more than 4 elements, so we proceed with the algorithm.

  2. Sort the Array: The array [1,5,6,14,15] is already in non-decreasing order.

  3. Calculate Potential Minimum Differences:

    • Scenario 1: Convert the three smallest elements (1, 5, 6) to the fourth smallest element (14). The new array looks like [14,14,14,14,15]. The difference is 15 - 14 = 1.
    • Scenario 2: Convert the three largest elements (6, 14, 15) to the fourth largest element (5). The new array looks like [1,5,5,5,5]. The difference is 5 - 1 = 4.
    • Scenario 3: Convert the largest element (15) to the second largest element (14), and the two smallest elements (1, 5) to the third smallest element (6). The new array looks like [6,6,6,14,14]. The difference is 14 - 6 = 8.
    • Scenario 4: Convert the two largest elements (14, 15) to the third largest element (6), and the smallest element (1) to the second smallest element (5). The new array looks like [5,5,6,6,6]. The difference is 6 - 5 = 1.
  4. Determine the Minimum Difference: The smallest difference among the calculated scenarios is 1.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

The primary operation in the algorithm is sorting the input array, which, for an array of length n, has a time complexity of in the average and worst cases. After sorting, the algorithm performs a constant number of operations to determine the minimum difference, resulting in a constant time complexity of . Therefore, the overall time complexity of the algorithm is dominated by the sorting step, making it .

Space Complexity

The space complexity of the algorithm is as the algorithm sorts the input array.

Minimum Difference Between Largest and Smallest Value in Three Moves (medium)
Letter Combinations of a Phone Number (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity